/**
 * Copyright 2009 Google Inc.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS-IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/* Remove non-cross-browser stuff I'm tempted to use */
if (Array.prototype.filter) delete Array.prototype.filter;
if (Array.prototype.forEach) delete Array.prototype.forEach;
if (Array.prototype.map) delete Array.prototype.map;
/* */

function busyWait(ms) {
  var start = (new Date()).getTime();
  while ((new Date()).getTime() < start+ms) {}
}

/*
    based on: http://www.JSON.org/json2.js
    2008-07-15
*/
toSource = function () {
  
  function f(n) {
    // Format integers to have at least two digits.
    return n < 10 ? '0' + n : n;
  }
  
  Date.prototype.toJSON = function (key) {

    return this.getUTCFullYear()   + '-' +
      f(this.getUTCMonth() + 1) + '-' +
      f(this.getUTCDate())      + 'T' +
      f(this.getUTCHours())     + ':' +
      f(this.getUTCMinutes())   + ':' +
      f(this.getUTCSeconds())   + 'Z';
  };

  String.prototype.toJSON =
    Number.prototype.toJSON =
    Boolean.prototype.toJSON = function (key) {
      return this.valueOf();
    };

  var cx = /[\u0000\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,
    escapeable = /[\\\"\x00-\x1f\x7f-\x9f\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,
    gap,
    indent,
    meta = {    // table of character substitutions
    '\b': '\\b',
    '\t': '\\t',
    '\n': '\\n',
    '\f': '\\f',
    '\r': '\\r',
    '"' : '\\"',
    '\\': '\\\\'
    },
    rep;


  function quote(string) {

    // If the string contains no control characters, no quote characters, and no
    // backslash characters, then we can safely slap some quotes around it.
    // Otherwise we must also replace the offending characters with safe escape
    // sequences.

    escapeable.lastIndex = 0;
    return escapeable.test(string) ?
      '"' + string.replace(escapeable, function (a) {
        var c = meta[a];
        if (typeof c === 'string') {
          return c;
        }
        return '\\u' + ('0000' +
                        (+(a.charCodeAt(0))).toString(16)).slice(-4);
      }) + '"' :
    '"' + string + '"';
  }


  function str(key, holder) {

    // Produce a string from holder[key].

    var i,          // The loop counter.
      k,          // The member key.
      v,          // The member value.
      length,
      mind = gap,
      partial,
      value = holder[key];

    // If the value has a toJSON method, call it to obtain a replacement value.

    if (value && typeof value === 'object' &&
        typeof value.toJSON === 'function') {
      value = value.toJSON(key);
    }

    // If we were called with a replacer function, then call the replacer to
    // obtain a replacement value.

    if (typeof rep === 'function') {
      value = rep.call(holder, key, value);
    }

    // What happens next depends on the value's type.

    switch (typeof value) {
    case 'string':
      return quote(value);

    case 'number':

      // JSON numbers must be finite. Encode non-finite numbers as null.

      return isFinite(value) ? String(value) : 'null';

    case 'boolean':
    case 'null':

      // If the value is a boolean or null, convert it to a string. Note:
      // typeof null does not produce 'null'. The case is included here in
      // the remote chance that this gets fixed someday.

      return String(value);

      // If the type is 'object', we might be dealing with an object or an array or
      // null.

    case 'object':

      // Due to a specification blunder in ECMAScript, typeof null is 'object',
      // so watch out for that case.

      if (!value) {
        return 'null';
      }

      // Make an array to hold the partial results of stringifying this object value.

      gap += indent;
      partial = [];

      // If the object has a dontEnum length property, we'll treat it as an array.

      if (typeof value.length === 'number' &&
          !(value.propertyIsEnumerable('length'))) {

	// The object is an array. Stringify every element. Use null as a placeholder
	// for non-JSON values.

        length = value.length;
        for (i = 0; i < length; i += 1) {
          partial[i] = str(i, value) || 'null';
        }

	// Join all of the elements together, separated with commas, and wrap them in
	// brackets.

        v = partial.length === 0 ? '[]' :
          gap ? '[\n' + gap +
          partial.join(',\n' + gap) + '\n' +
          mind + ']' :
          '[' + partial.join(',') + ']';
        gap = mind;
        return v;
      }

      // If the replacer is an array, use it to select the members to be stringified.

      if (rep && typeof rep === 'object') {
        length = rep.length;
        for (i = 0; i < length; i += 1) {
          k = rep[i];
          if (typeof k === 'string') {
            v = str(k, value);
            if (v) {
              partial.push(quote(k) + (gap ? ': ' : ':') + v);
            }
          }
        }
      } else {

	// Otherwise, iterate through all of the keys in the object.

        for (k in value) {
          if (Object.hasOwnProperty.call(value, k)) {
            v = str(k, value);
            if (v) {
              partial.push(quote(k) + (gap ? ': ' : ':') + v);
            }
          }
        }
      }

      // Join all of the member texts together, separated with commas,
      // and wrap them in braces.

      v = partial.length === 0 ? '{}' :
        gap ? '{\n' + gap + partial.join(',\n' + gap) + '\n' +
        mind + '}' : '{' + partial.join(',') + '}';
      gap = mind;
      return v;
    }
  }

  return function (value, replacer, space) {

      // The stringify method takes a value and an optional replacer, and an optional
      // space parameter, and returns a JSON text. The replacer can be a function
      // that can replace values, or an array of strings that will select the keys.
      // A default replacer method can be provided. Use of the space parameter can
      // produce text that is more easily readable.

      var i;
      gap = '';
      indent = '';

      // If the space parameter is a number, make an indent string containing that
      // many spaces.

      if (typeof space === 'number') {
        for (i = 0; i < space; i += 1) {
          indent += ' ';
        }

	// If the space parameter is a string, it will be used as the indent string.

      } else if (typeof space === 'string') {
        indent = space;
      }

      // If there is a replacer, it must be a function or an array.
      // Otherwise, throw an error.

      rep = replacer;
      if (replacer && typeof replacer !== 'function' &&
          (typeof replacer !== 'object' ||
           typeof replacer.length !== 'number')) {
        throw new Error('JSON.stringify');
      }

      // Make a fake root object containing our value under the key of ''.
      // Return the result of stringifying the value.

      return str('', {'': value});
  }
}();

function debugFrame(optName, func) {
  var name = "something";
  if ((typeof optName) == "string") {
    name = optName;
  }
  else func = optName;

  return function() {
    try {
      return func.apply(this, arguments);
    }
    catch (e) {
      console.warn(name+" didn't complete");
      throw e;
    }
  }
}

function makeRecentSet(size) {
  var ringBuffer = {};
  var nextIndex = 0;
  return {
    contains: function (elem) {
      for(var i=0;i<size;i++) {
	if (ringBuffer[i] === elem) return true;
      }
      return false;
    },
    addNew: function (elem) {
      // precond: not already in set
      ringBuffer[nextIndex] = elem;
      nextIndex = ((nextIndex+1) % size);
    }
  };
}
